def fib(n):
    '''generate a fibonacci series'''
    a, b = 0, 1
    for i in range(n + 1):
        a, b = b, a + b
    return a


def test_point_count(delta):
    n = 0
    while fib(n) < int(1/delta)+1:
        n += 1
    return n


def fib_search(a=None, b=None, delta=None, func=None):
    n = test_point_count(delta)  # find the amount of test points
    F = [fib(i) for i in range(n + 1)]
    # print(n)
    # print(F)

    # case k=1, initialize
    tl = b + F[n - 1] / F[n] * (a - b)
    tr = a + F[n - 1] / F[n] * (b - a)

    for k in range(2, n-1):
        if func(tl) < func(tr):
            a, b, tr = a, tr, tl
            tl = b+F[n-k]/F[n-k+1]*(a-b)
        else:
            a, b, tl = tl, b, tr
            tr = a+F[n-k]/F[n-k+1]*(b-a)
        print('a=%.3f, b=%.3f, tl=%.3f, tr=%.3f' % (a, b, tl, tr))

    # case k=n-1
    if func(tl) < func(tr):
        a, b = a, tr
    else:
        a, b = tl, b
    tl, tr = 1 / 2 * (a + b), a + (1 / 2 + 0.01) * (b - a)
    print('a=%.3f, b=%.3f, tl=%.3f, tr=%.3f' % (a, b, tl, tr))
    return tl if func(tl) < func(tr) else tr


def f(t): return t ** 2 - t + 2


res = fib_search(a=-1, b=3, delta=0.08, func=f)
print('近似极小点为%.3f，近似极小值为%.3f' % (res, f(res)))
